#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;

int n,m;
int scc[N],sum,low[N],dfn[N],cnt,tot[N];
int dp[N],degree[N];
ll res;

struct node{
	int v,val;
};

vector<node> adj[N];
vector<node> nadj[N];
bool ok[N];
stack<int> s;

void Tarjan(int u){
	dfn[u]=low[u]=++cnt;
	ok[u]=true;
	s.push(u);

	for(auto [v,val]:adj[u]){
		if(dfn[v]==0){
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}else{
			if(ok[v]){
				low[u]=min(low[u],dfn[v]);
			}
		}
	}

	if(dfn[u]==low[u]){
		sum++;
		scc[u] = sum;
		ok[u] = false;
		tot[sum]++;

		while(s.top()!=u){
			ok[s.top()]=false;
			scc[s.top()]=sum;
			s.pop();
			tot[sum]++;
		}
		s.pop();
	}
}

void solve(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,u,v;
		cin>>x>>u>>v;
		if(x==1){
			adj[u].push_back({v,0});
			adj[v].push_back({u,0});
		}else if(x==2){
			adj[u].push_back({v,1});
		}else if(x==3){
			adj[v].push_back({u,0});
		}else if(x==4){
			adj[v].push_back({u,1});
		}else{
			adj[u].push_back({v,0});
		}
	}

	for(int i=1;i<=n;i++){
		if(!dfn[i])Tarjan(i);
	}

	for(int i=1;i<=n;i++){
		for(auto [v,val]:adj[i]){
			int xx=scc[i];
			int yy=scc[v];

			if(xx==yy && v==1){
				cout<<-1<<'\n';
				return;
			}

			if(xx!=yy){
				nadj[xx].push_back((node){yy,val});
				degree[yy]++;
			}
		}
	}

	queue<int> q;

	for(int i=1;i<=n;i++){
		if(!degree[i]){
			q.push(i);
			dp[i]=1;
			degree[i]=0;
		}
	}

	while(!q.empty()){
		int u=q.front();
		q.pop();

		for(auto [v,val]:adj[u]){
			degree[v]--;
			dp[v]=max(dp[v],dp[u]+val);

			if(!degree[v])q.push(v);
		}
	}

	for(int i=1;i<=sum;i++){
		res+=dp[i]*tot[i];
	}

	cout<<res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}